2.1 Hierarchical Vector Quantization

2.1.3 Quantization Error

Let us try to understand quantization error with an example.

Figure 1: The Voronoi tessellation for level 1 shown for the 5 cells with the points overlayed

An example of a 2 dimensional VQ is shown above.

In the above image, we can see 5 cells with each cell containing a certain number of points. The centroid for each cell is shown in blue. These centroids are also known as codewords since they represent all the points in that cell. The set of all codewords is called a codebook.

Now we want to calculate quantization error for each cell. For the sake of simplicity, let’s consider only one cell having centroid A and m data points \(F_i\) for calculating quantization error.

For each point, we calculate the distance between the point and the centroid.

\[ d = ||A - F_i||_{p} \]

In the above equation, p = 1 means L1_Norm distance whereas p = 2 means L2_Norm distance. In the package, the L1_Norm distance is chosen by default. The user can pass either L1_Norm, L2_Norm or a custom function to calculate the distance between two points in n dimensions.

\[QE = \max_i(||A-F_i||_{p})\]

Now, we take the maximum calculated distance of all m points. This gives us the furthest distance of a point in the cell from the centroid, which we refer to as Quantization Error. If the Quantization Error is higher than the given threshold, the centroid/ codevector is not a good representation for the points in the cell. Now we can perform further Vector Quantization on these points and repeat the above steps.

Please note that the user can select mean, max or any custom function to calculate the Quantization Error. The custom function takes a vector of m value (where each value is a distance between point in n dimensions and centroids) and returns a single value which is the Quantization Error for the cell.

If we select mean as the error metric, the above Quantization Error equation will look like this:

\[QE = \frac{1}{m}\sum_{i=1}^m||A-F_i||_{p}\]

7.1 Step 1: Data Compression

Note: The steps of compression, projection, and tessellation are iteratively performed until a minimum compression rate of 80% is achieved. Once the desired compression is attained, the resulting model object is used for scoring using the scoreHVT() function

The core function for compression in the workflow is HVQ, which is called within the trainHVT function. we have a parameter called quantization error. This parameter acts as a threshold and determines the number of levels in the hierarchy. It means that, if there are ‘n’ number of levels in the hierarchy, then all the clusters formed till this level will have quantization error equal or greater than the threshold quantization error. The user can define the number of clusters in the first level of hierarchy and then each cluster in first level is sub-divided into the same number of clusters as there are in the first level. This process continues and each group is divided into smaller clusters as long as the threshold quantization error is met. The output of this technique will be hierarchically arranged vector quantized data.

However, let’s try to comprehend the trainHVT function first before moving on.

trainHVT(
  data,
  min_compression_perc,
  n_cells,
  depth,
  quant.err,
  normalize = TRUE,
  distance_metric = c("L1_Norm", "L2_Norm"),
  error_metric = c("mean", "max"),
  quant_method = c("kmeans", "kmedoids"),
  dim_reduction_method = c("sammon" , "tsne" , "umap")
  scale_summary = NA,
  diagnose = FALSE,
  hvt_validation = FALSE,
  train_validation_split_ratio = 0.8,
  projection.scale,
  tsne_perplexity,tsne_theta,tsne_verbose,
  tsne_eta,tsne_max_iter,
  umap_n_neighbors,umap_min_dist
)

Each of the parameters of trainHVT function have been explained below:

• data - A dataframe, with numeric columns (features) that will be used for training the model.

• min_compression_perc - An integer, indicating the minimum compression percentage to be achieved for the dataset. It indicates the desired level of reduction in dataset size compared to its original size.

• n_cells - An integer, indicating the number of cells per hierarchy (level). This parameter determines the granularity or level of detail in the hierarchical vector quantization.

• depth - An integer, indicating the number of levels. A depth of 1 means no hierarchy (single level), while higher values indicate multiple levels (hierarchy).

• quant.err - A number indicating the quantization error threshold. A cell will only breakdown into further cells if the quantization error of the cell is above the defined quantization error threshold.

• normalize - A logical value indicating if the dataset should be normalized. When set to TRUE, scales the values of all features to have a mean of 0 and a standard deviation of 1 (Z-score)

• distance_metric - The distance metric can be L1_Norm(Manhattan) or L2_Norm(Euclidean). L1_Norm is selected by default. The distance metric is used to calculate the distance between a datapoint and its centroid.

• error_metric - The error metric can be mean or max. max is selected by default. max will return the max of m values and mean will take mean of m values where each value is a distance between a point and centroid of the cell.

• quant_method - The quantization method can be kmeans or kmedoids. Kmeans uses means (centroids) as cluster centers while Kmedoids uses actual data points (medoids) as cluster centers. kmeans is selected by default.

• dim_reduction_method - The dimensionality reduction method to be chosen. options are ‘tsne’ , ‘umap’ & ‘sammon’. Default is ‘sammon’.

• scale_summary - A list with user defined mean and standard deviation values for all the features in the dataset. Pass the scale summary when normalize is set to FALSE.

• diagnose - A logical value indicating whether user wants to perform diagnostics on the model. Default value is FALSE.

• hvt_validation - A logical value indicating whether user wants to holdout a validation set and find mean absolute deviation of the validation points from the centroid. Default value is FALSE.

• train_validation_split_ratio - A numeric value indicating train validation split ratio. This argument is only used when hvt_validation has been set to TRUE. Default value for the argument is 0.8.

• projection.scale - A number indicating the scale factor for the tessellations to visualize the sub-tessellations well enough. It helps in adjusting the visual representation of the hierarchy to make the sub-tessellations more visible. Default is 10.

• tsne_perplexity - A numeric, balances the attention t-SNE gives to local and global aspects of the data. Lower values focus more on local structure, while higher values consider more global structure. It is recommended to be between 5 and 50. Default value is 30.

• tsne_theta - A numeric, speed/accuracy trade-off parameter for Barnes-Hut approximation. If set to 0, exact t-SNE is performed, which is slower. If set to greater than 0, an approximation is used, which speeds up the process but may reduce accuracy. Default value is 0.5

• tsne_eta (learning_rate) - A numeric, learning rate for t-SNE optimization.Determines the step size during optimization. If too low, the algorithm might get stuck in local minima; if too high, the solution may become unstable. Default value is 200.

• tsne_max_iter - An integer, maximum number of iterations. Number of iterations for the optimization process. More iterations can improve results but increase computation time. Default value is 1000.

• umap_n_neighbors - An integer, the size of the local neighborhood (in terms of number of neighboring sample points) used for manifold approximation, controls the balance between local and global structure in the data, smaller values focus on local structure, while larger values capture more global structures. Default value is 15.

• umap_min_dist - A numeric, the minimum distance between points in the embedded space, controls how tightly UMAP packs points together, lower values result in a more clustered embedding. Default value is 0.1

The output of trainHVT function (list of 7 elements) have been explained below with an image attached for clear understanding.

NOTE: Here the attached image is the snapshot of output list generated from iteration 1 which can be referred later in this section

Figure 3: The Output list generated by trainHVT function.

• The ‘1st element’ is a list containing information related to plotting tessellations. This information might include coordinates, boundaries, or other details necessary for visualizing the tessellations

• The ‘2nd element’ is a list containing information related to Sammon’s projection coordinates of the data points in the reduced-dimensional space.

• The ‘3rd element’ is a list containing detailed information about the hierarchical vector quantized data along with a summary section containing no of points, Quantization Error and the centroids for each cell for 2D.

• The ‘4th element’ is a list that contains all the diagnostics information of the model when diagnose is set to TRUE. Otherwise NA.

• The ‘5th element’ is a list that contains all the information required to generates a Mean Absolute Deviation (MAD) plot, if hvt_validation is set to TRUE. Otherwise NA

• The ‘6th element’ is a list containing detailed information about the hierarchical vector quantized data along with a summary section containing no of points, Quantization Error and the centroids for each cell which is the output of hvq.

• The ‘7th element’ (model info) is a list that contains model generated timestamp, input parameters passed to the model, validation results and the dimensionality reduction evaluation metrics table.

We will use the trainHVT function to compress our data while preserving essential features of the dataset. Our goal is to achieve data compression upto atleast 80%. In situations where the compression ratio does not meet the desired target, we can explore adjusting the model parameters as a potential solution. This involves making modifications to parameters such as the quantization error threshold or increasing the number of cells and then rerunning the trainHVT function again.

In our example we will iteratively increase the number of cells until the desired compression percentage is reached instead of increasing the quantization threshold because it may reduce the level of detail captured in the data representation

Iteration 1:

We will pass the below mentioned model parameters along with torus training dataset (containing 9600 datapoints) to trainHVT function.

Model Parameters

• Number of Cells at each Level = 100
• Maximum Depth = 1
• Quantization Error Threshold = 0.1
• Error Metric = Max
• Distance Metric = Euclidean
• Dimensionality Reduction method = Sammon

hvt.torus <- trainHVT(
  torus_train,
  n_cells = 100,
  depth = 1,
  quant.err = 0.1,
  normalize = FALSE,
  distance_metric = "L2_Norm",
  error_metric = "max",
  quant_method = "kmeans",
  dim_reduction_method = "sammon")

summary(hvt.torus)

As it can be seen from the table above, none of the 100 cells have reached the quantization threshold error. Therefore we can further subdivide the cells by increasing the n_cells parameters and then see if desired compression (80%) is reached

Let’s take a look on the 1D projection of this iteration. The output of hvq from the trainHVT function is then passed to the plotHVT function, which applies Sammon’s 1D using MASS package. The resulting 1D Sammon’s points are used to determine their corresponding cell IDs and subsequently plotted in a plotly object.

plotHVT(hvt.torus, plot.type = '1D')

Iteration 2:

Let’s retry by increasing the n_cells parameter to 300 for torus training dataset (containing 9600 datapoints).

Model Parameters

• Number of Cells at each Level = 300
• Maximum Depth = 1
• Quantization Error Threshold = 0.1
• Error Metric = Max
• Distance Metric = Euclidean
• Dimensionality Reduction method = Sammon

hvt.torus2 <- trainHVT(
  torus_train,
  n_cells = 300,
  depth = 1,
  quant.err = 0.1,
  normalize = FALSE,
  distance_metric = "L2_Norm",
  error_metric = "max",
  quant_method = "kmeans",
  dim_reduction_method = "sammon"
)

summary(hvt.torus2)

It can be observed from the table above that only 143 cells out of 300 i.e. 48% of the cells reached the Quantization Error threshold. Therefore we can further subdivide the cells by increasing the n_cells parameters and then see if 80% compression is reached

plotHVT(hvt.torus2, plot.type = '1D')

Iteration 3:

Since we are yet to achieve the compression of atleast 80%, lets try again by increasing the n_cells parameter to 500 for torus training dataset (containing 9600 datapoints) .

Model Parameters

• Number of Cells at each Level = 500
• Maximum Depth = 1
• Quantization Error Threshold = 0.1
• Error Metric = Max
• Distance Metric = Euclidean
• Dimensionality Reduction method = Sammon

set.seed(240)
hvt.torus3 <- trainHVT(
  torus_train,
  n_cells = 500,
  depth = 1,
  quant.err = 0.1,
  normalize = FALSE,
  distance_metric = "L2_Norm",
  error_metric = "max",
  quant_method = "kmeans",
  dim_reduction_method = "sammon"
)

summary(hvt.torus3)

By increasing the number of cells to 500, we were successfully able to compress 90% of the data, so we will not further subdivide the cells

We successfully compressed data to 90% using n_cells parameter as 500, the next step involves performing data projection on the compressed data. In this step, the compressed data will be transformed and projected onto a lower-dimensional space to visualize and analyze the data in a more manageable form.

plotHVT(hvt.torus3, plot.type = '1D')

7.2 Step 2: Data Projection

This section focusses on projecting the sammon’s dimensionality reduction from multi dimension to 2D. The following plots will have the centroids plotted in 2D space with x coordinate of the centroid points on X-axis and y coordinate of the centroid points on Y-axis.

Now let’s try to understand plotHVT function. The parameters have been explained in detail below:

plotHVT <-(hvt.results, line.width, color.vec, pch1, centroid.size,
           title, maxDepth, child.level, hmap.cols, centroid.color,
           quant.error.hmap, n_cells.hmap, cell_id, 
           label.size, sepration_width, layer_opacity,
           dim_size, plot.type = '2Dhvt') 

• hvt.results - (1D/2Dproj/2Dhvt/2Dheatmap/surface_plot) A list obtained from the trainHVT function. This list provides an overview of the hierarchical vector quantized data, including diagnostics, tessellation details, Sammon’s projection coordinates, and model input information.

• line.width - (2Dhvt/2Dheatmap) A vector indicating the line widths of the tessellation boundaries for each layer.

• color.vec - (2Dhvt/2Dheatmap) A vector indicating the colors of the tessellations boundaries at each layer.

• pch1 - (2Dhvt/2Dheatmap) Symbol. It plots the centroids with a particular symbol such as (solid circle, bullet, filled square, filled diamond) in the tessellations.(default = 21 i.e filled circle).

• centroid.size - (2Dhvt/2Dheatmap) Vector of Size of centroids for each level of tessellations.

• centroid.color - (2Dhvt/2Dheatmap) Vector of color of centroids for each level of tessellations.

• title - (2Dhvt) Set a title for the plot (default = NULL).

• maxDepth - (2Dhvt) An integer indicating the number of levels.

• cell_id - (2Dhvt) Logical. To indicate whether the plot should have Cell IDs or not for the level 1. (default = FALSE)

• child.level - (2Dheatmap/surface_plot) A Number indicating the level for which the heat map is to be plotted.

• hmap.cols - (2Dheatmap/surface_plot) A Number or a Character which is the column number of column name from the dataset indicating the variables for which the heat map is to be plotted.

• label.size - (2Dheatmap) The size by which the tessellation labels should be scaled.(default = 0.5)

• quant.error.hmap - (2Dheatmap) A number indicating the quantization error threshold.

• n_cells.hmap - (2Dheatmap) An integer indicating the number of cells/clusters per hierarchy

• sepration_width - (surface_plot) An integer indicating the width between two levels.

• layer_opacity - (surface_plot) A vector indicating the opacity of each layer/level.

• dim_size - (surface_plot) An integer indicating the dimension size used to create the matrix for the plot.

• plot.type - A Character indicating which type of plot should be generated. Accepted entries are ‘1D’, ‘2Dproj’,‘2Dhvt’,‘2Dheatmap’ & ‘surface_plot’. Default value is ‘2Dhvt’.

Iteration 1:

Lets see the projected Sammons 2D onto a plane with n_cell set to 100 in first iteration.

plotHVT(hvt.torus, plot.type = '2Dproj')

Figure 7: Sammons 2D Plot for 100 cells

Iteration 2:

Lets see the projected Sammons 2D onto a plane with n_cell set to 300 in second iteration.

plotHVT(hvt.torus2, plot.type = '2Dproj')

Figure 8: Sammons 2D Plot for 300 cells

Iteration 3:

Lets see the projected Sammons 2D onto a plane with n_cell set to 500 in third iteration.

plotHVT(hvt.torus3, plot.type = '2Dproj')

Figure 9: Sammons 2D Plot for 500 cells

7.3 Step 3: Tessellation

The deldir package computes the Delaunay triangulation (and hence the Dirichlet or Voronoi tessellation) of a planar point set according to the second (iterative) algorithm of Lee and Schacter. For subsequent levels, transformation is performed on the 2D coordinates to get all the points within its parent tile. Tessellations are plotted using these transformed points as centroids. plotHVT is the main function to plot hierarchical voronoi tessellation.

Iteration 1:

To enhance visualization, let’s generate a plot of the Voronoi tessellation for the first iteration where we set n_cells parameter as 100. This plot will provide a visual representation of the Voronoi regions corresponding to the data points, aiding in the analysis and understanding of the data distribution.

plotHVT(
  hvt.torus,
  line.width = c(0.4),
  color.vec = c("black"),
  centroid.size = 0.6,
  maxDepth = 1, 
  plot.type = '2Dhvt')

Figure 10: The Voronoi tessellation for layer 1 shown for the 100 cells in the torus training dataset

Iteration 2:

Now, let’s plot the Voronoi tessellation for the second iteration where we set n_cells parameter to 300.

plotHVT(
  hvt.torus2,
  line.width = c(0.4),
  color.vec = c("black"),
  centroid.size = 0.6,
  maxDepth = 1,
  plot.type = '2Dhvt'
)

Figure 11: The Voronoi tessellation for layer 1 shown for the 300 cells in the torus training dataset

Iteration 3:

Now, let’s plot the Voronoi tessellation again, for the third iteration where we set n_cells parameter to 500.

plotHVT(
  hvt.torus3,
  line.width = c(0.4),
  color.vec = c("black"),
  centroid.size = 0.6,
  maxDepth = 1,
  plot.type = '2Dhvt'
)

Figure 12: The Voronoi tessellation for layer 1 shown for the 500 cells in the torus training dataset

From the presented plot, the inherent structure of the donut can be easily observed in the two-dimensional space

7.3.1 Heat Maps

Now let’s plot the Voronoi Tessellation with the heatmap overlaid for all the features in the torus data for better visualization and interpretation of data patterns and distributions.

The heatmaps displayed below provides a visual representation of the spatial characteristics of the torus, allowing us to observe patterns and trends in the distribution of each of the features (x,y,z). The sheer green shades highlight regions with higher coordinate values in each of the heatmaps, while the indigo shades indicate areas with the lowest coordinate values in each of the heatmaps. By analyzing these heatmaps, we can gain insights into the variations and relationships between each of these features within the torus structure.

plotHVT(
  hvt.torus3,
  child.level = 1,
  hmap.cols = "n",
  line.width = c(0.4),
  color.vec = c("black"),
  centroid.size = 0.8,
  plot.type = '2Dheatmap'
)

Figure 13: The Voronoi tessellation for layer 1 and number of cells 500 with the heat map overlaid for No. of entities in each cell in the torus dataset

plotHVT(
  hvt.torus3,
  child.level = 1,
  hmap.cols = "x",
  line.width = c(0.4),
  color.vec = c("black"),
  centroid.size = 0.8,
  plot.type = '2Dheatmap'
)

Figure 14: The Voronoi tessellation for layer 1 and number of cells 500 with the heat map overlaid for variable x in the torus dataset

plotHVT(
  hvt.torus3,
  child.level = 1,
  hmap.cols = "y",
  line.width = c(0.4),
  color.vec = c("black"),
  centroid.size = 0.8,
  plot.type = '2Dheatmap'
)

Figure 15: The Voronoi tessellation for layer 1 and number of cells 500 with the heat map overlaid for variable y in the torus dataset

plotHVT(
  hvt.torus3,
  child.level = 1,
  hmap.cols = "z",
  line.width = c(0.4),
  color.vec = c("black"),
  centroid.size = 0.8,
  plot.type = '2Dheatmap'
)

Figure 16: The Voronoi tessellation for layer 1 and number of cells 500 with the heat map overlaid for variable z in the torus dataset

7.4 Step 4: Scoring(scoreHVT)

Let’s try to comprehend the scoreHVT function first before moving on

scoreHVT(dataset,
         hvt.results.model,
         child.level,
         mad.threshold,
         line.width,
         color.vec,
         normalize,
         distance_metric,
         error_metric,
         yVar,
         analysis.plots,
         names.column)

The parameters for the function scoreHVT are explained below:

• dataset - A dataframe containing the testing dataset. The dataframe should have all the variable(features) used for training.

• hvt.results.model - A list obtained from the trainHVT function while performing hierarchical vector quantization on training data. This list provides an overview of the hierarchical vector quantized data, including diagnostics, tessellation details, Sammon’s projection coordinates, and model input information.

• child.level - A number indicating the depth for which the heat map is to be plotted. Each depth represents a different level of clustering or partitioning of the data.

• mad.threshold - A numeric value indicating the permissible Mean Absolute Deviation which is obtained from Minimum Intra centroid plot(when diagnose is set to TRUE in trainHVT). mad.threshold value is important since it is used in anomaly detection.Default value is 0.2 NOTE: for a given datapoint, when the quantization error is above mad.threshold it is denoted as anomaly else not.

• line.width - A vector indicating the line widths of the tessellation boundaries for each layer. (Optional Parameters)

• color.vec - A vector indicating the colors of the tessellations boundaries at each layer. (Optional Parameters)

• normalize - A logical value indicating if the dataset should be normalized. When set to TRUE, the data (testing dataset) is standardized by mean and sd of the training dataset referred from the trainHVT(). When set to FALSE, the data is used as such without any changes.

• distance_metric - The distance metric can be L1_Norm(Manhattan) or L2_Norm(Euclidean). The metric is used when calculating distance between each datapoint(in test dataset) with the centroids obtained from results of trainHVT. Default is L1_Norm.

• error_metric - The error metric can be mean or max. max will return the max of m values and mean will take mean of m values where each value is a distance between the datapoint and centroid of the cell. This helps in calculating the scored quantization error. Default value is max.

• yVar - A character or a vector representing the name of the dependent variable(s)

The below given arguments are used only when character column can be mapped over the scored results. since torus doesn’t have a character column, we are not using them in this vignette.

• analysis.plots - A logical value to indicate whether to include the insight plots which are useful in viewing the contents and clusters of cells. Default is FALSE.

• names.column - The column of names of the datapoints which will be displayed as the contents of the cell in ‘scoredPlotly’. Default is NULL.

Now once we have built the model, let us try to score using our testing dataset (containing 2400 data points) which cell and which level each point belongs to.

scoring_torus <- scoreHVT(
  torus_test,
  hvt.torus3,
  child.level = 1,
  line.width = c(1.2),
  color.vec = c("black"),
  normalize = FALSE)

summary(scoring_torus)